import string
import copy

def stringToList(strang):
	dalist=[]
	for x in range(0,len(strang)):
		dalist.append(strang[x])
	return dalist

def getSubStrings(full_word,curr_word,used_list):
	substrings=[]
	for x in range(0,len(full_word)):
		if used_list.count(x)==0:
			new_curr_word = curr_word+full_word[x]
			new_used_list = copy.copy(used_list)
			new_used_list.append(x)
			substrings.append(new_curr_word)
			substrings.extend(getSubStrings(full_word,new_curr_word,new_used_list))
	return substrings

def getWordsR(word):
	substrings=getSubStrings(word,"",[])
	substrings.sort()

	x=0
	y=0

	words=[]
	while x<len(dictionary) and y<len(substrings):
		while x<len(dictionary) and substrings[y]>dictionary[x]:
			x+=1

		if x<len(dictionary) and dictionary[x]!=word and substrings[y]==dictionary[x]:
			words.append(substrings[y])

		y+=1

	return words

def getWords(word):
	words = []
	lessthanequalword = []
	for i in range(0,len(dictionary)):
		if len(dictionary[i]) <= len(word):
			lessthanequalword.append(dictionary[i])

	for j in range(0,len(lessthanequalword)):
		if inword(lessthanequalword[j],word) and word != lessthanequalword[j]:
			words.append(lessthanequalword[j])

	return words
		

def inword(subs, words):
	sub=stringToList(subs)
	word=stringToList(words)

	sub.sort()
	word.sort()

	i = 0
	j = 0

	while j < len(sub):
		if i == len(word):
			return False
		
		if word[i] > sub[j]:
			return False
		elif word[i] == sub[j]:
			i += 1
			j += 1
 	
		elif word[i] < sub[j]:
			i += 1


	return True	

dictionary=[]
file = open("lowerwords.txt",'r')

for line in file:
	dictionary.append(line.strip())

file.close()

dictionary.sort()

word="peregrinoandrewrobertniidantaninelson"
#print getWordsR(word)
print getWords(word)
